#include<vector>
#include<iostream>
using namespace std;

void  inster_sort(vector<int>& arr)
{
    //先写一步的
    //首先我们需要将比当前这个数大的元素向前移
    //就是将前边的元素移到当前位置所以就要有一个变量进行存储当前元素的下标
    //当然我们还需要一个end变量来指示我们比到哪里了？因为我们最后是放到我们第一个比那个大的数的后边
    //即比的下标加一
    for(int i = 1;i < arr.size();i++)
    {
        int cur = i;
        int end = cur - 1;
        int tem = arr[cur];
        while(end >= 0)
        {
            
            if(tem < arr[end])
            {
                arr[end + 1] = arr[end];
                end--;
 
            }
            else{
                break;
            }
        }
        arr[end + 1] = tem;
    }
   
}
void shell_sort(vector<int> & arr)
{
    //进行分量的确定
    int gap = arr.size();
    while(gap > 1)
    {
        gap /= 2;
        for(int i = 0;i < arr.size() - gap;i++)
        {
            int cur = arr[i + gap];
            int end = i;
            while(end >= 0)
            {
                if(cur < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = cur;
        }
    }
}
int main()
{
    //希尔排序的主要原理其实跟插入排序差不多的
    //只不过插入排序的话是每个数间隔一步，而希尔排序是间隔不断减小的插入排序
    //所以说我们先要对插入排序有一定的理解才能对希尔排序理解的更加透彻。
    vector<int>arr;
    int n = 0;
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        int tem = 0;
        cin >> tem;
        arr.push_back(tem);
    }
    shell_sort(arr);
    //inster_sort(arr);
    for(auto j : arr)
    {
        cout << j << ' ';
    }
    return 0;

}